package org.cos.generation.util.agorithm;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import org.cos.generation.epda.State;
import org.cos.generation.epda.State.Transition;

public class NullTransitionRemoving {

	public static int remove(State states[], List<Set<Integer>> reachedList) {
		int size = states.length;
		
		List<List<Transition>> addedTransList = new ArrayList<List<Transition>>(size);
		for (int i = 0; i < size; i++) addedTransList.add(new LinkedList<Transition>());
	
		// Remove the null transitions and mark unreachable states.
		boolean[] reachable = new boolean[size];
		reachable[0] = true; 
		for (int i = 0; i < size; i++) {
			State state = states[i];
			if (state != null) {
				List<Transition> transitions = state.getTransitions();
				for (Iterator<Transition> it = transitions.iterator();
						it.hasNext();) {
					Transition trans = it.next();
					if (trans.getMethod() == null) {
						it.remove();
					} else {
						reachable[trans.getTailIndex()] = true;
					}
				}
				for (Integer head : reachedList.get(i)) {
					addedTransList.get(head).addAll(transitions);
				}
			}
		}
		
		// Compact states list.
		int newIndex[] = new int[size];
		int offset = 0;
		for (int i = 0; i < size; i++) {
			if (!reachable[i]) {
				states[i] = null;
				offset++;
			} else {
				states[i].getTransitions().addAll(addedTransList.get(i));
				states[i-offset] = states[i];
				newIndex[i] = i-offset;
			}
		}
		size -= offset;
		
		return size;
	}
	
}
